/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 18, 2014
 */
package zhoujian.oj.leetcode;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a string s and a dictionary of words dict, determine if s
 *              can be segmented into a space-separated sequence of one or more
 *              dictionary words.
 * 
 *              For example, given s = "leetcode", dict = ["leet", "code"].
 * 
 *              Return true because "leetcode" can be segmented as "leet code".
 */
public class WordBreak {
	
	@Test
	public void testWordBreak() {
		Set<String> dict = new HashSet<String>();
		dict.add("leet");
		dict.add("code");
		System.out.println(wordBreak("leetcode", dict));
	}

	// using dynamic programming
	public boolean wordBreak(String s, Set<String> dict) {
		if (s == null || s.length() == 0)
			return true;
		if (dict.size() == 0)
			return false;
		
		// seg[i, j] means substring starting from i and length is j
		boolean[][] seg = new boolean[s.length()][s.length() + 1];
		for (int len = 1; len <= s.length(); len++) {
			for (int i = 0; i + len <= s.length(); i++) {
				String temp = s.substring(i, i + len);
				if (dict.contains(temp)) {
					seg[i][len] = true;
					continue;
				}
				for (int k = 1; k < len; k++) {
					if (seg[i][k] && seg[i + k][len - k]) {
						seg[i][len] = true;
						break;
					}
				}
			}
		}
		
		return seg[0][s.length()];
	}
	
	@Test
	public void testSolution2() {
		Set<String> dict = new HashSet<String>();
		dict.add("leet");
		dict.add("code");
		dict.add("abc");
		dict.add("dab");
		dict.add("ca");
		System.out.println(solution2("leetcodeabcdabca", dict));
	}

	// better solution
	// O(s.len * dict.size)
	public boolean solution2(String s, Set<String> dict) {
		// f[i] means substring starting from 0 and length is i
		boolean[] f = new boolean[s.length() + 1];
		f[0] = true;
		
		for (int i = 0; i < s.length(); i++) {
			// should continue from match position
			if (!f[i])
				continue;
			
			for (String a : dict) {
				int len = a.length();
				int end = i + len;
				if (end > s.length())
					continue;
				if (s.substring(i, end).equals(a))
					f[end] = true;
			}
		}
		
		return f[s.length()];
	}
}
